The deniable zero-knowledge interactive proof technique in a random oracle model is disclosed in some inventions, notable of which is Literature 1. The art of Literature 1 (hereinafter, “Related Art 1”) will be described below.
FIG. 4 is an illustrative diagram which shows the configuration disclosed in Literature 1. In the drawings accompanying the present application, merging arrows indicate that all the information at the sources of these arrows is merged together and sent to the single destination of these arrows. A forked arrow indicates that all or part of the information at the source of this arrow is sent to the multiple respective destinations of this arrow.
A language proved by Related Art 1 is an NP-complete 3-graph coloring problem, where a “language” refers to a set of data. The reference that a language is a “3-graph coloring problem” means that a set of data is a set of 3-graph coloring problems. Proving that a “d” belongs to a language (e.g., a set of 3-graph coloring problems) is equivalent to proving that a “d” belongs to a set of 3-graph coloring problems. That Related Art 1 can prove this language with deniable zero-knowledge means that Related Art 1 can prove all languages belonging to NP with deniable zero-knowledge.
As a common input 101, the proving apparatus 103 and the verification apparatus 104, shown in FIG. 4, receive input of a directional graph Gn=(VG, EG), where VG is a set of graph vertices, EG is a set of graph sides, and the graph G is expressed by both VG and EG. The number of vertices (which is denoted as |VG|) is expressed as |VG|=n.
The proving apparatus 103 receive input of the colors of vertices C=(c1, c2, . . . , cn) as an evidence 102. iε{1, . . . , n} each is ciε{1, 2, 3}, which indicates the three colors, thereby expressing the different colors of vertices. C is colored so that, for all the sides, two vertices connected by a side are in different colors from each other.
The proving apparatus 103 proves to the verification apparatus 104 that the above-mentioned evidence C really exists with respect to G, by performing a deniable zero-knowledge interactive proof. Performing an “interactive proof” means the following. If C having the property described above does not exist with respect to G, then whatever false proving apparatus may be used, the verification apparatus (verification apparatus 104 in this example) would ultimately not output a signal which indicates that it will accept the proof, after the false proving apparatus and the verification apparatus (verification apparatus 104 in this example) communicate with each other and perform respective calculations. If G and C are inputted into the proving apparatus (proving apparatus 103 in this example) and the verification apparatus (verification apparatus 104 in this example), the verification apparatus (verification apparatus 104 in this example) outputs a signal which indicates that it will accept the proof.
Being a deniable zero-knowledge means the following. Whatever false verification apparatus may communicate with the proving apparatus (proving apparatus 103 in this example), outputs from this false verification apparatus always satisfy the property described below (property A), regardless of whatever data has been inputted into the false verification apparatus and even thought the false verification apparatus operates in polynomial time only; provided that the false verification apparatus can concurrently communicate with a plurality of proving apparatuses which have been given the same G and C. The property A is a property in which, if a simulation apparatus exists which can communicate with a false verification apparatus and which operates in polynomial time only, and if an input into the false verification apparatus is given to the simulation apparatus, the simulation apparatus can output data from which the output from the false verification apparatus and its distribution are unidentifiable even though the simulation apparatus is unable to communicate with the proving apparatus (proving apparatus 103 in this example). A concrete example of property A will be described below. This example assumes, as an example, that an arbitrary false verification apparatus outputs some data after communicating with the proving apparatus (proving apparatus 103 in this example). The data will be referred to as “data a” in the following description. The simulation apparatus also communicates with the false verification apparatus (during which the simulation apparatus behaves as a proving apparatus) and then outputs some data. The data will be referred to as “data b” in the following description. Whatever false verification apparatus may be used, the simulation apparatus can output the distribution of its output data, data a, as well as data b having an unidentifiable distribution (property A).
The reference that the distribution of data a and the distribution of data b are unidentifiable means the following. Suppose that the distribution A of certain data and the distribution B of another data are given. Data a is data which has been selected from the distribution A uniformly and randomly, while data b is data which has been selected from the distribution B uniformly and randomly. Whatever identification apparatus D (which outputs either 0 or 1) may be used, the distribution of data a and that of data b are unidentifiable if the probability that the identification apparatus D outputs 1 when a is inputted into the identification apparatus D is the same as the probability that the identification apparatus D outputs 1 when b is inputted into the identification apparatus D. The probability is obtained by selecting different pairs of a and b from the distributions A and B repeatedly.
Next, the operations of the proving apparatus 103 and the verification apparatus 104 shown in FIG. 4 will be described. While the following description shows an example in which a discrete logarithm problem is used, a general (probabilistic) one-way function can also be used. Gq is a multiplicative group in which a discrete logarithm problem for an order q is difficult, and g is its generator. t is a safety variable. It suffices for t to have a value of 160 or higher. Hash (•) is a hash function and its output size is denoted as t bits.
Step 1: The verification apparatus 104 randomly selects xεZ/qZ and calculates y=gx.
Step 2: The verification apparatus 104 selects x′[i]εZ/qZ with respect to i=1, . . . , t and sets y′[i]=gx′[i].
Step 3: The verification apparatus 104 selects random numbers r[1, i]ε{0, 1}n and r[2, i]ε{0, 1}n with respect to i=1, . . . , t. With respect to i=1, . . . , t, the verification apparatus 104 generates hash values c[1, i]=Hash(x′[i], r[1, i]) and c[2, i]=Hash(x′[i]+x, r[2, i]) by communicating many times with an apparatus 105 which generates hash functions.
Step 4: The verification apparatus 104 calculates a t-bit hash value c using the following equation.h=Hash({g, y, y′[i], c[1, i], c[2,i]}i=1, . . . , t)
If the i-th bit of h is 0, the verification apparatus 104 sets t[1, i]=x′[i] and t[2, i]=r[1, i] with respect to i=1, . . . , t. If the i-th bit of h is 1, the verification apparatus 104 sets t[1, i]=x′[i]+x and t [2, i]=r[2, i]).
Step 5: The verification apparatus 104 sends {g, y, y′[i], c[1, i], c[2, i], t[1, i], t[2, i]}=1, . . . , t) to the proving apparatus 103.
Step 6: The proving apparatus 103 calculates h′=Hash({g, y, y′[i], c[1, i], c[2, i]} i=1, . . . , t). By communicating with an apparatus 107 which calculates a hash function, the proving apparatus 103 verifies with respect to i=1, . . . , t that c[1, i]=Hash(t[1, i], t[2, i]) and gt[1, i]=y′[i] if the i-th bit of h′is 0 and c[2, i]=Hash(t[1, i], t[2, i]) and gt[2, i]=y·y′[i] if the i-th bit of h′is 1.
Step 7: The proving apparatus 103 generates a non-interactive zero-knowledge proof in which a hash function 107 is used, in order to prove that it knows x in y=gx or knows C with respect to G. At this time, the proving apparatus 103 proves this in such a manner that which one of these it knows is not identifiable. The non-interactive zero-knowledge proof in Step 7 is generated according to, for example, the method described in Literature 3.
Step 8: The proving apparatus 103 sends the non-interactive zero-knowledge proof generated in Step 7 to the verification apparatus 104.
Step 9: The verification apparatus 104 verifies the non-interactive zero-knowledge proof sent from the proving apparatus 103. If the proof is correct, the verification apparatus 104 accepts it. Otherwise, the verification apparatus 104 outputs as a verification result 109 a signal which indicates non-acceptance of the proof.
Assuming that a hash function is a function which returns random data, Steps 1 to 5 collectively represent a non-interactive zero-knowledge proof by the verification apparatus 104 to prove that the verification apparatus 104 knows x. Whether or not the verification apparatus 104 knows x can be determined as follows.
The data sent from the proving apparatus 103 should be as described below with respect to h′=Hash({g, y, y′[i], c [1, i], c [2, i]} i=1, . . . , t).
That is, with respect to i=1, . . . , t, if the i-th bit of h′is 0, the equations c[1, i]=Hash(t[1, i], t[2, i]) and gt[1, i]=y′[i] should hold true; if the i-th bit of h′is 1, the equations c[2, i]=Hash(t[1, i], t[2, i]) and gt[2, i]=y·y′[i] should hold true.
Such data can easily be generated as long as the value of h′ has been predetermined. This kind of assumption is possible if the hash function is assumed to be a function which returns a random number, and therefore the data can be generated even though x is unknown. In this case, the proving apparatus 103 will not be able to obtain any knowledge from this data.
The fact that a proof as described above represents an interactive proof between the proving apparatus 103 and the verification apparatus 104 is clear from the following. In Step 7, the proving apparatus 103 proves to the verification apparatus 104 that, with respect to G, (1) it knows C, i.e., C exists with respect to G, or (2) it knows x. However, since no knowledge can be obtained from the data received in Step 5, the proving apparatus 103 is unable to obtain the discrete log of Gq and therefore z remains unknown to the proving apparatus 103. Thus, it is necessary to prove (1) above.
The fact that the interaction between the proving apparatus 103 and the verification apparatus 104 in the operation described above represents deniable zero-knowledge is clear from the following. In a random oracle model, when the verification apparatus 104 calculates hash values c[1, i]=Hash(x′[i], r[1, i]) and c[2, i]=Hash(x′[i]+x, r[2, i]), it must send both (x′[i], r[1, i]) and (x′[i]+x, r[2, i]) to the random oracle. If a simulation apparatus intercepts these values, it can easily obtain x by performing a simple calculation: (x′[i]+x)−x′[i]=x. Once the simulation apparatus gains knowledge of x, it can make a proof of (2) above (i.e., it knows x) in Step 7. This proof is not identifiable from a proof of (1) above (i.e., it knows C). This means that the simulation apparatus can generate data that is unidentifiable from the data generated by the proving apparatus 103.
In the operation above, a deniable zero-knowledge interactive proof between the proving apparatus 103 and the verification apparatus 104 consists of two rounds of communication. In other words, the proof only requires a total of two communications: one from the verification apparatus 104 to the proving apparatus 103 and the other from the proving apparatus 103 to the verification apparatus 104.
The special honest verifier zero-knowledge interactive proof technique is disclosed, for example, in Literature 2. A “special honest verifier” implies that data sent by a verifier (verification apparatus) to a prover (proving apparatus) is a random number. In a special honest verifier zero-knowledge interactive proof, three messages are used: a message aR, which is initially sent from the proving apparatus to the verification apparatus, a message eR, which is then sent from the verification apparatus to the proving apparatus, and a message zR, which is finally sent from the proving apparatus to the verification apparatus. A “proof commitment” is a message aR, which is initially sent to the verification apparatus. A “challenge value” is a message eR, which is then sent from the verification apparatus to the proving apparatus. A “response” is a message zR, which is finally sent from the proving apparatus to the verification apparatus.
The art of Literature 2 (hereinafter, “Related Art 2”) will now be described below. FIGS. 5 and 6 are illustrative diagrams which show the configurations disclosed in Literature 2. In the description below, a relationship is denoted by R, a common input (common input 207 in FIG. 5 and FIG. 6) by X, and an evidence (evidence 208 in FIG. 6) by W. (X, W)εR indicates that a common input X and an evidence W satisfy a relationship R.
The proof commitment generation apparatus 201 shown in FIG. 5 is an apparatus which generates a proof commitment using a function AR. The response generation apparatus 202 is a function which generates a response using a function ZR. The verification apparatus 203 is an apparatus which outputs a verification result using a function VR. The simulation apparatus 204 shown in FIG. 6 is an apparatus which performs an operation of a function SR. The evidence extraction apparatus 205 is an apparatus which extracts an evidence using a function ER. The functions AR, ZR, VR, SR and ER will be described later.
A 3-round special honest verifier zero-knowledge interactive proof with respect to the relationship R is denoted as SHVZKIP(R). This proof uses the function AR for generation of a proof commitment, the function ZR for generation of a response, the function VR for verification, the function SR for simulation and the function ER for extraction of an evidence. It satisfies the property described below, where Rp and RS are random tapes:
(First Property)
Suppose that the challenge value eR (challenge value 212 in the diagram) is a random number 206. Also suppose that the proof commitment aR (proof commitment 209 in the diagram) and the response zR (response 210 in the diagram) are respectively expressed by the equations below:aR=AR(X, W, Rp)zR=ZR(X, W, Rp, eR)Then VR=VR(X, ap, eR, ZR)=1 holds true, where an output from VR is called a verification result 211.(Second Property)
Suppose that the proof commitment aR (proof commitment 213 in the diagram), the first challenge value eR and the second challenge value e′R (pair of the first and second challenge values 214 in the diagram) and the first response zR and the second response z′R (pair of the first and second responses 215) satisfy the following equations:VR(X, aR, eR, zR)=1VR(X, aR, e′R, z′R)=1eR≠e′R 
Then (X, W′)εR holds true for the evidence W′ (evidence 216 in the diagram), where W′=ER(aR, eR, zR, e′R, z′R)
(Third Property)
Suppose the challenge value eR (challenge value 212 in the diagram) is a random number. Also suppose that the proof commitment aR (commitment 209 in the diagram proof) and the response zR (response 210 in the diagram) are expressed by the following equations, where Rp is a random tape 206:aR=AR(X ,W, Rp)zR=ZR(X, W, Rp, eR)
On the other hand, suppose that the challenge value e′R (challenge value 216 in the diagram) is a random number. Also suppose that the proof commitment a′R (proof commitment 217 in the diagram) and the response z′R (response 218 in the diagram) are derived by the following equations, where RS is a random tape 219:(a′R, z′R)=SR(X, e′R, RS)
In this context, the distribution of (aR, eR, zR) obtained by randomly allocating the random tape Rp (random tape 206 in the diagram) and the distribution of (a′R, e′R, z′R) obtained by randomly allocating the random tape RS (random tape 219 in the diagram) are difficult to be identified from each other.
Although an interactive proof performed by using SHVZKIP(R) involves a constraint that an eR selected by the verification apparatus must be random, such interactive proof is not zero-knowledge because there is generally no guarantee that the verification apparatus will always select an eR that is random.
However, there are many known SHVZKIP(R)'s that are efficient enough. It is thus meaningful in terms of application to use one of such SHVZKIP(R)'s to constitute a zero-knowledge interactive proof with a minimum decrease in efficiency.
An example of SHVZKIP(R) is shown below.
Suppose that X is the two elements (y,g) of Gq and W is the element x of Z/qZ, and that (X,W)εR if a relationship y=gx is satisfied.
The function AR may be a function, for example, as follows. The input of the function AR are X, W and the random tape Rp. The function AR generates x′ εZ/qZ, which is random, from Rp and outputs aR for aR=y′=gx′.
The function ZR may be a function, for example, as follows. The input of the function ZR are X, W, the random tape Rp and eR=c. The function ZR calculates zR=r=xc+x′ mod q and outputs zR.
The function VR may be a function, for example, as follows. The input of the function VR are X, aR, eR and zR. The function VR outputs 1 if gr=yc y′ holds true; otherwise, it outputs 0.
The function ER may be a function, for example, as follows. The input of the function ER are aR, eR=c, zR=r, e′R=c′and z′R=r′. The function ER calculates W=x=(r−r′)/(c′−c) mod q and outputs W.
The function SR may be a function, for example, as follows. The input of the function SR are X, eR=c and the random tape RS. The function RS generates zR=rεZ/qZ, which is random, from RS and also generates aR=y′=gry−c It then outputs (aR,zR).
(Non-Interactive Knowledge Proof)
A non-interactive knowledge proof will be explained below. In Related Art 2 described above, a prover proves to a verifier that an instance belongs to a certain language through an interaction (communication) between the proving apparatus and the verification apparatus. There is another method of proving that an instance belongs to a certain language. In this method, a prover is required to send data to a verifier only once. This is called a non-interactive proof. In particular, a proof designed to prove in polynomial time that the prover has an evidence with which it can be verified that an instance belongs to a certain language is called a non-interactive knowledge proof.
According to the method described in Literature 3, an example (PR) of non-interactive knowledge proof which proves to X that the prover knows R as expressed by (X,W)εR by using a special honest verifier zero-knowledge interactive proof can be formed as follows.PR=(aR, zR)
where Rp is a random tape. It is assumed that the following relationships hold true:aR=AR(X, W, Rp),eR=Hash(X, aR),aR=AR(X, W, Rp, eR).
Literature 1: “Rafael Pass”, “On Deniability in the Common Reference String and Random Oracle Model”, “CRYPTO 2003”,2003, p.316-337, p316-337
Literature 2: “Oded Goldreich”, “Foundations of Cryptography—Basic Tools”, “Cambridge University Press”,2001, p.206-207
Literature 3: “Amos Fiat Adi Shamir”, “How to Prove Yourself Practical Solutions to Identification and Signature Problems”, “CRYPTO 1986”, 1986, p.186-194
However, Related Art 1 has problems as described below.
In Related Art 1, it is necessary in Step 3 to generate, with respect to a sufficiently large t, at number of commitment{c[1, i] and c[2, i]}i=1, . . . , t. The reason for this is as follows. A simulation apparatus needs committed values x′[i] and x′[i]+x for both of the two commitments c[1, i]=Hash(x′[i], r[1, i]) and c[2, i]=Hash(x′[i]+x, r[2, i]). This means that the simulation apparatus will not work properly unless both the commitments are created correctly. During the operation of an actual verification apparatus, however, only one of the committed values is disclosed for each i. Therefore, the proving apparatus may not be aware if the hidden one of the committed values has been generated illegally. In order to avoid this problem, Related Art 1 generates a commitment for each of a sufficiently large number (t) of i's, so that the probability that the verification apparatus can cheat the proving apparatus with respect to all i's will be decreased to a sufficiently low level (½t).
For this reason, Related Art requires a verification apparatus to generate a large number of commitments and, in Step 6, requires a proving apparatus to perform a large number of calculations. These requirements lead to a drawback that calculation time as well as communication traffic between these apparatuses are increased.
As explained in the description of Related Art 1, Steps 1 to 5 represent a non-interactive zero-knowledge proof for discrete log knowledge. A comparison of this proof against the below-described non-interactive zero-knowledge proof for discrete log knowledge would reveal a large difference in the amounts of calculation and communication traffic between these proofs.
Suppose that y=gx. The proving apparatus receives input of g, y, and x, while the verifier (verification apparatus) receives input of g and y.
Step 1: The proving apparatus selects x′εZ/qZ and generates y′=gx′.
Step 2: The proving apparatus calculates c=Hash(g, y, y′).
Step 3: The proving apparatus calculates t=c x+x′ mod q.
Step 4: The proving apparatus sends (t, c) to the verification apparatus.
Step 5: The verification apparatus verifies that c=Hash(g, y, gty−c) holds.
Although communications and calculations in the non-interactive zero-knowledge proof shown above are those utilized in Related Art 1, the amounts of communications and calculations are merely at a level around 1/t times the amounts required by Related Art 1, implying a very high operational efficiency.
However, the method shown above cannot immediately be applied to the method according to Related Art 1, because although the simulation apparatus may retrieve the input (g, y, y′) into the hash, it cannot obtain x from these values.
Related Art 2, on the other hand, provides many efficient methods for many R's but does not have the zero-knowledge nature, as described at the end of the description for Related Art 2. In particular, it would never have the nature of deniable zero-knowledge.
The present invention has been made to address the above-described problems. The object of the present invention is to enable a deniable zero-knowledge interactive proof which requires low amounts of communications and calculations when a method of special honest verifier zero-knowledge interactive proof is given.